package skiplist

import (
	"fmt"
	"math/rand"
	"time"
)

const (
	maxLevel = 5
)

type Item struct {
	Key   int
	Value int
}

type node struct {
	item Item
	next []*node
}

type SkipList struct {
	level int
	head  *node
	r     *rand.Rand
}

func newNode(level, key, value int) *node {
	return &node{
		item: Item{
			Key:   key,
			Value: value,
		},
		next: make([]*node, level),
	}
}

func New() *SkipList {
	sl := new(SkipList)

	head := newNode(maxLevel, 0, 0)
	sl.head = head
	sl.level = 0

	source := rand.NewSource(time.Now().Unix())
	sl.r = rand.New(source)
	return sl
}

func (sl *SkipList) randomLevel() int {
	level := 1
	for sl.r.Int()%2 != 0 {
		level++
	}

	if level > maxLevel {
		level = maxLevel
	}

	return level
}

func (sl *SkipList) Insert(key, value int) {
	var (
		q      *node = nil
		p            = sl.head
		update       = make([]*node, maxLevel)
	)

	for i := sl.level - 1; i >= 0; i-- {
		for q = p.next[i]; q != nil && q.item.Key < key; q = p.next[i] {
			p = q
		}

		update[i] = p
	}

	level := sl.randomLevel()
	if level > sl.level {
		for i := sl.level; i < level; i++ {
			update[i] = sl.head
		}
		sl.level = level
	}

	q = newNode(level, key, value)
	for i := level - 1; i >= 0; i-- {
		q.next[i] = update[i].next[i]
		update[i].next[i] = q
	}
}

func (sl *SkipList) Delete(key int) bool {
	var (
		update       = make([]*node, maxLevel)
		q      *node = nil
		p            = sl.head
	)

	for i := sl.level - 1; i >= 0; i-- {
		for q = p.next[i]; q != nil && q.item.Key < key; q = p.next[i] {
			p = q
		}

		update[i] = p
	}

	if q == nil || q.item.Key != key {
		return false
	}

	for i := sl.level - 1; i >= 0; i-- {
		if update[i].next[i] == q {
			update[i].next[i] = q.next[i]
			if sl.head.next[i] == nil {
				sl.level--
			}
		}
	}

	return true
}

func (sl *SkipList) Find(key int) *Item {
	var (
		q *node = nil
		p       = sl.head
	)

	for i := sl.level - 1; i >= 0; i-- {
		for q = p.next[i]; q != nil && q.item.Key < key; q = p.next[i] {
			p = q
		}
		if q != nil && q.item.Key == key {
			return &q.item
		}
	}

	return nil
}

func (sl *SkipList) Print() {
	p := sl.head.next[0]

	for ; p != nil; p = p.next[0] {
		fmt.Println(p.item.Key, p.item.Value)
	}
}
